package skiplist;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import project1driver.SetData;
import readfile.ReadStringFile;

public class SkipList<E, K extends Comparable<K>>
{
	// SkipList Data
	private int numberOfElements;
	private SkipNode<E, K> topLeftNode;
	private int height;
	private ArrayList<SkipNode<E, K>> listOfLevels;
	
	private static long startTime;
	private static long duration;
	private static long minTime;
	private static long maxTime;
	private static long aveTime;
	private static long time_sum;
	private SetData skip_data;
	private ArrayList<SkipNode<E, K>> skip_elements;
	
	public SkipList()
	{
		skip_data = new SetData("Skip");
		skip_elements = new ArrayList<SkipNode<E, K>>(0);
		numberOfElements = 0;
		height = 0;
		listOfLevels = new ArrayList<SkipNode<E, K>>(0);
		
		// Create level 0 and the top left sentinel
		listOfLevels.add(new SkipNode<E, K>());
		topLeftNode = listOfLevels.get(0);
		
		// Add right sentinel and connect to left sentinel
		topLeftNode.right = new SkipNode<E, K>();
		topLeftNode.right.left = topLeftNode;
	}
	
	public void resetTime()
	{
		startTime = 0;
		duration = 0;
		minTime = 0;
		maxTime = 0;
		aveTime = 0;
		time_sum = 0;
	}
	
	public SetData runtest(Object[] fileData, int[] randomIndices)
	{
		resetTime();
		
		// Insert data
		for(int i = 0; i < fileData.length; i++)
		{
			startTime = System.nanoTime();
			this.insertData((E) fileData[i], (K) fileData[i]);
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		skip_data.insert_results[0] = minTime;
		skip_data.insert_results[1] = aveTime;
		skip_data.insert_results[2] = maxTime;
		
		// Search data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			skip_elements.add(search((K) fileData[randomIndices[i]]));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		skip_data.search_results[0] = minTime;
		skip_data.search_results[1] = aveTime;
		skip_data.search_results[2] = maxTime;
		
		// Predecessor data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			predecessor(skip_elements.get(i));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		skip_data.pred_results[0] = minTime;
		skip_data.pred_results[1] = aveTime;
		skip_data.pred_results[2] = maxTime;
		
		// Successor data
		resetTime();
		
		for(int i = 0; i < 10; i++)
		{
			startTime = System.nanoTime();
			successor(skip_elements.get(i));
			duration = System.nanoTime() - startTime;
			
			if(minTime == 0)
			{
				minTime = duration;
			}
			else if(duration < minTime)
			{
				minTime = duration;
			}
			
			if(maxTime == 0)
			{
				maxTime = duration;
			}
			else if(duration > maxTime)
			{
				maxTime = duration;
			}
			
			time_sum = time_sum + duration;
		}
		
		aveTime = time_sum / fileData.length;
		
		skip_data.succ_results[0] = minTime;
		skip_data.succ_results[1] = aveTime;
		skip_data.succ_results[2] = maxTime;
		
		// Maximum data
		resetTime();
		startTime = System.nanoTime();
		maximum();
		duration = System.nanoTime() - startTime;
		
		skip_data.timeOfMax = duration;
		
		// Minimum data
		resetTime();
		startTime = System.nanoTime();
		minimum();
		duration = System.nanoTime() - startTime;
		
		skip_data.timeOfMin = duration;
		
		
		return skip_data;
	}
	
	public SkipNode<E, K> after(SkipNode<E, K> node)
	{
		return node.right;
	}
	
	public SkipNode<E, K> before(SkipNode<E, K> node)
	{
		return node.left;
	}
	
	public SkipNode<E, K> above(SkipNode<E, K> node)
	{
		return node.top;
	}
	
	public SkipNode<E, K> below(SkipNode<E, K> node)
	{
		return node.bottom;
	}
	
	public int getHeight()
	{
		return height;
	}
	
	/**
	 * size
	 * 
	 * Description: returns the number of elements in the set
	 * @return
	 */
	public int size()
	{
		return numberOfElements;
	}
	
	/**
	 * insertNewLevel
	 * 
	 * Description: inserts a new level below the current top level
	 * 
	 * @return
	 */
	private SkipNode<E, K> insertNewLevel()
	{
		listOfLevels.add(new SkipNode<E, K>());
		height = height + 1;
		SkipNode<E, K> newTopLeft = listOfLevels.get(height);
		
		// Connect new top left node to the old top left node
		// and to the new right sentinel
		
		// Connect new top left node to old topleftnode
		newTopLeft.bottom = topLeftNode;
		newTopLeft.right = new SkipNode<E, K>();
		newTopLeft.right.left = newTopLeft;
		
		topLeftNode.top = newTopLeft;
		
		// Assign the top left node 
		topLeftNode = newTopLeft;
		
		return topLeftNode.bottom;
	}
	
	/**
	 * insertData
	 * 
	 * Description: public wrapper method to insert a node
	 * @param nodeData
	 * @param nodeKey
	 */
	public void insertData(E nodeData, K nodeKey)
	{
		insert(new SkipNode<E, K>(nodeData, nodeKey));
	}
	
	/**
	 * insert
	 * 
	 * Description: method to insert a new node
	 * 
	 * @param nodeToInsert
	 */
	public void insert(SkipNode<E, K> nodeToInsert)
	{
		if(height == 0)
		{
			insertNewLevel();
		}
		
		SkipNode<E, K> searchResultNode = search(nodeToInsert.key);
		SkipNode<E, K> positionOfNewNode 
			= insertAfterAbove(searchResultNode, null, nodeToInsert.data, nodeToInsert.key);
		
		while(Math.random() < 0.5)
		{
			while(searchResultNode.top == null)
			{
				if(searchResultNode.left != null)
				{
					searchResultNode = searchResultNode.left;
				}
			}
			
			searchResultNode = searchResultNode.top;
			if(searchResultNode == topLeftNode)
			{
				searchResultNode = insertNewLevel();
			}
			
			positionOfNewNode 
				= insertAfterAbove(searchResultNode, positionOfNewNode, nodeToInsert.data, nodeToInsert.key);
		}
		
		numberOfElements++;
	}
	
	/**
	 * insertAfterAbove
	 * 
	 * Description: inserts a node after previousNode and above belowNode
	 *  
	 * @param previousNode
	 * @param belowNode
	 * @param nodeToAdd
	 * @return
	 */
	private SkipNode<E,K> insertAfterAbove(
				SkipNode<E, K> previousNode, 
				SkipNode<E, K> belowNode,
				E data,
				K key)
	{
		SkipNode<E, K> nodeToAdd = new SkipNode<E, K>(data, key);
		
		// Insert new node after previousnode
		nodeToAdd.right = previousNode.right;
		nodeToAdd.left = previousNode;
		previousNode.right.left = nodeToAdd;
		previousNode.right = nodeToAdd;
		
		// Insert new node above belownode
		if(belowNode != null)
		{
			nodeToAdd.top = belowNode.top;
			nodeToAdd.bottom = belowNode;
			belowNode.top = nodeToAdd;
		}
		
		return nodeToAdd;
	}
	
	public boolean deleteKey(K searchKey)
	{
		SkipNode<E, K> result = search(searchKey);
		boolean keyDeleted = false;
		
		if(result != null)
		{
			delete(result);
			keyDeleted = true;
		}
		
		return keyDeleted;
	}
	
	/**
	 * delete
	 * 
	 * Description: deletes a node from the set
	 * @param nodeToDelete
	 */
	public void delete(SkipNode<E, K> nodeToDelete)
	{
		if(nodeToDelete != null)
		{
			while(nodeToDelete != null)
			{
				if(nodeToDelete.left != null && nodeToDelete.left.right != null)
				{
					nodeToDelete.left.right = nodeToDelete.right;
				}
				
				if(nodeToDelete.right != null && nodeToDelete.right.left != null)
				{
					nodeToDelete.right.left = nodeToDelete.left;
				}
				nodeToDelete = nodeToDelete.top;
			}
			numberOfElements = numberOfElements - 1;
			deleteExtraLevels();
		}
	}
	
	/**
	 * deleteExtraLevels
	 * 
	 * Description: deletes empty levels below the top level
	 */
	private void deleteExtraLevels()
	{
		while(topLeftNode.bottom != null && topLeftNode.bottom.right.key == null)
		{
			topLeftNode = topLeftNode.bottom;
			listOfLevels.remove(height);
			height = height - 1;
		}
	}
	
	/**
	 * searchForKey
	 * 
	 * Description: public wrapper method to search for a key
	 * @param searchKey
	 * @return
	 */
	public K searchForKey(K searchKey)
	{
		SkipNode<E, K> result = search(searchKey);
		
		if(result != null && result.key.compareTo(searchKey) == 0)
		{
			return result.key;
		}
		else
		{
			return null;
		}
	}
	
	/**
	 * search
	 * 
	 * Description: method to search for a key
	 * returns the node less than OR equal to the key
	 * @param searchKey
	 * @return
	 */
	public SkipNode<E, K> search(K searchKey)
	{
		SkipNode<E, K> tempnode = topLeftNode;
		
		while(tempnode.bottom != null)
		{
			tempnode = tempnode.bottom;
			
			while(tempnode.right.key != null && tempnode.right.key.compareTo(searchKey) <= 0)
			{
				tempnode = tempnode.right;
			}
		}
		
		return tempnode;
	}
	
	public SkipNode<E, K> minimum()
	{
		SkipNode<E, K> min = listOfLevels.get(0).right;
		if(min.key == null)
		{
			min = null;
		}
		return min;
	}
	
	public SkipNode<E, K> maximum()
	{
		SkipNode<E, K> max = listOfLevels.get(0).right;
		if(max.key == null)
		{
			max = null;
		}
		else
		{
			while(max.right.key != null)
			{
				max = max.right;
			}
		}
		
		return max;
	}
	
	/**
	 * findSuccessor
	 * 
	 * Description: public wrapper method to search for the successor of a key
	 * 
	 * @param searchKey
	 * @return
	 */
	
	public K findSuccessor(K searchKey)
	{
		SkipNode<E, K> result = search(searchKey);
		
		// If the key is found, then get the successor
		if(result != null && result.key.compareTo(searchKey) == 0)
		{
			result = successor(result);
			return result.key;
		}
		else
		{
			return null;
		}
	}
	
	public SkipNode<E, K> successor(SkipNode<E, K> node)
	{	
		if(node != null)
		{
			node = node.right;
		}
		
		return node;
	}
	
	/**
	 * findPredecessor
	 * 
	 * Description: public wrapper method to find a predecessor of a key
	 * 
	 * @param searchKey
	 * @return
	 */
	public K findPredecessor(K searchKey)
	{
		SkipNode<E, K> result = search(searchKey);
		
		// If the key is found, then get the predecessor
		if(result != null && result.key.compareTo(searchKey) == 0)
		{
			result = predecessor(result);
			return result.key;
		}
		else
		{
			return null;
		}
	}
	
	public SkipNode<E, K> predecessor(SkipNode<E, K> node)
	{
		if(node != null)
		{
			node = node.left;
		}
		return node;
	}
	
	public String toString()
	{
		String printedString = null;
		SkipNode<E, K> tempNode;
		
		for(int i = height; i >= 0; i--)
		{
			tempNode = listOfLevels.get(i);
			while(tempNode != null)
			{
				if(printedString == null)
				{
					printedString = tempNode.toString() + " - ";
				}
				else if(tempNode.right == null)
				{
					printedString = printedString.concat(tempNode.toString());
				}
				else
				{
					printedString = printedString.concat(tempNode.toString() + " - ");
				}
				
				tempNode = tempNode.right;
			}
			printedString = printedString.concat("\n\n");
		}
		
		return printedString;
	}
	
	private static class SkipNode<E, K extends Comparable<K>> implements Comparable<SkipNode<E, K>>
	{
		// SkipNode Data
		private SkipNode<E, K> top, bottom, left, right;
		
		private E data;
		private K key;
		
		private SkipNode()
		{
			top = null;
			bottom = null;
			left = null;
			right = null;
			
			data = null;
			key = null;
		}
		
		private SkipNode(E data, K key)
		{
			top = null;
			bottom = null;
			left = null;
			right = null;
			
			this.data = data;
			this.key = key;
		}
		
		private SkipNode(E data, K key, 
				SkipNode<E, K> topNode, SkipNode<E, K> bottomNode,
				SkipNode<E, K> leftNode, SkipNode<E, K> rightNode)
		{
			top = topNode;
			bottom = bottomNode;
			left = leftNode;
			right = rightNode;
			this.data = data;
			this.key = key;
		}
		
		public int compareTo(SkipNode<E, K> nodeToCompare)
		{
			return this.key.compareTo(nodeToCompare.key);
		}
		
		public String toString()
		{
			if(key != null)
			{
				return key.toString();
			}
			return "SENTINEL";
		}
		
	}
	
 	
 	public static void main(String[] args)
 	{
 		char command = '0';
		Scanner readInput = new Scanner(System.in);
		String key = null;
		String data = null;
		SkipNode<String, String> searchResult = null;
		String keyAndData;
		
		SkipList<String, String> testList = new SkipList<String, String>();
		
		readInput.useDelimiter("\n");
		
		System.out.println("Unit test for DLLDynamicSet and DLLNode\n");
		
		while(command != 'q')
		{
			System.out.print(
					"\n\n\n******   Command Menu   ******\n\n" +
					"1) Insert item\n" +
					"2) Delete item\n" +
					"3) Get size of list\n" +
					"4) Get minimum\n" +
					"5) Get maximum\n" +
					"6) Find successor\n" +
					"7) Find predecessor\n" +
					"8) Print keys\n" +
					"9) Read data from file\n" +
					"q) Quit\n\n" +
					": "
					);
			command = readInput.next().toCharArray()[0];
			
			switch(command)
			{
			case '1':
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test insert   ******" + "\n" +
						"Enter node data: "
						);
				data = readInput.next();
				
				System.out.print("Enter node key: ");
				key = readInput.next();
				
				testList.insert(new SkipNode<String, String>(
						data, key));
				
				break;
			case '2':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Test delete   ******" + "\n" +
						"Enter key: "
						);
				key = readInput.next();
				
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					testList.delete(searchResult);
					System.out.println("Key deleted.");
				}
				else
				{
					System.out.println("Key not found.");
				}
				
				break;
			case '3':
				System.out.print("\n\n******   Size of list ******\n" +
						"Number of elements: " + testList.size()
						);
				break;
			case '4':
				System.out.print("\n\n******   Get minimum   ******\n" +
						"Minimum key: " + testList.minimum()
						);
				break;
			case '5':
				System.out.print("\n\n******   Get maximum   ******\n" +
						"Maximum key: " + testList.maximum()
						);
				break;
			case '6':
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find successor   ******\n" +
						"Enter key: "
						);
				
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Successor: " + testList.successor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				
				break;
			case '7': 
				searchResult = null;
				data = null;
				key = null;
				
				System.out.print("\n\n******   Find predecessor   ******\n" +
						"Enter key: "
						);
				key = readInput.next();
				searchResult = testList.search(key);
				if(searchResult != null)
				{
					System.out.println("Predecessor: " + testList.predecessor(searchResult));
				}
				else
				{
					System.out.println("Key not found");
				}
				break;
			case '8':
				System.out.println(testList);
				break;
			case '9':
				System.out.print("\n\n******   Read data from file   ******" + "\n" +
						"Enter a file name: "
						);
				ReadStringFile fileToRead = new ReadStringFile(readInput.next());
				try {
					while(fileToRead.hasLine())
					{
						keyAndData = fileToRead.readLine();
						testList.insert(new SkipNode<String, String>(keyAndData, keyAndData));
					}
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				break;
			case 'q':
				System.out.println("Exiting program...");
				break;
			default:
				System.out.println("Please choose a valid option.");
			}
			
		}
 	}
}
